#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/18 21:01
# @USER    : Shengji He
# @File    : Permutations.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        """
        Given a collection of distinct integers, return all possible permutations.

        Example:
            Input: [1,2,3]

            Output:

            [
              [1,2,3],      \n
              [1,3,2],      \n
              [2,1,3],      \n
              [2,3,1],      \n
              [3,1,2],      \n
              [3,2,1]       \n
            ]

        :param nums:
        :return:
        """
        iterator = self.combinations(nums, len(nums))
        ans = []
        while True:
            try:
                ans.append(next(iterator))
            except StopIteration:
                break
        return ans

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        """
        Given a collection of numbers that might contain duplicates, return all possible unique permutations.

        Example:
            Input: [1,1,2]

            Output:

            [
              [1,1,2],      \n
              [1,2,1],      \n
              [2,1,1]       \n
            ]

        :param nums:
        :return:
        """
        iterator = self.combinations(nums, len(nums))
        ans = []
        while True:
            try:
                temp = next(iterator)
                if temp not in ans:
                    ans.append(temp)
            except StopIteration:
                break
        return ans

    def combinations(self, items, n):
        def skipIthItem(items, i):
            return items[:i] + items[i + 1:]

        return self.__combinators(skipIthItem, items, n)

    def __combinators(self, _handle, items, n):
        if n == 0:
            yield []
        for i, item in enumerate(items):
            this_one = [item]
            for cc in self.__combinators(_handle, _handle(items, i), n - 1):
                yield this_one + cc


if __name__ == '__main__':
    S = Solution()
    # 0046
    nums = [1, 2, 3]
    print(S.permute(nums))

    # 0047
    nums = [1, 1, 2]
    print(S.permuteUnique(nums))
    print('done')
